package com.company.algo.niuke;

import java.util.Arrays;

/**
 * 合并两个有序的数组
    【不知道怎么不利用额外空间了】
 忽略了题目中是【有序数组】
 所以可以逆向思维，从右往左推，将大的元素先填满A的空白区间
 */
public class MergeTwoOrderedArrays {
    //归并
    public void merge1(int A[], int m, int B[], int n) {
        int Alen = A.length;
        int[] res = new int[Alen];
        int i = 0, j = 0, k=0;
        while(i<m && j<n){
            if(A[i]>B[j]) res[k++] = B[j++];
            else res[k++] = A[i++];
        }
        while(i<m) res[k++] = A[i++];
        while(j<n) res[k++] = B[j++];
        for (i = 0;  i<Alen ; i++) {
            A[i] = res[i];
        }
    }
    public void merge(int A[], int m, int B[], int n) {
        int place = m-- + n-- -1;
        while(m>=0 && n>=0){
            A[place--] = A[m]>B[n]?A[m--]:B[n--];
        }
        while(n>=0) A[place--] = B[n--];    //注意这是>=0，因为初始化的时候就将之减去了1
    }
    public static void main(String[] args) {
        MergeTwoOrderedArrays Main = new MergeTwoOrderedArrays();
        int[] A = {0};
        int[] B = {1};
        int m = 0;
        int n = 1;
        Main.merge(A,m,B,n);
        System.out.println(Arrays.toString(A));
    }
}
